<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,100分)- 精准核酸检测（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4>在线OJ刷题</h4> 
<p><a href="https://hydro.ac/d/HWOD2023/p/OD398" rel="nofollow" title="题目详情 - 精准核酸检测 - Hydro">题目详情 - 精准核酸检测 - Hydro</a></p> 
<p></p> 
<h4 id="main-toc">题目描述</h4> 
<p>为了达到新冠疫情精准防控的需要&#xff0c;为了避免全员核酸检测带来的浪费&#xff0c;需要精准圈定可能被感染的人群。</p> 
<p>现在根据传染病流调以及大数据分析&#xff0c;得到了每个人之间在时间、空间上是否存在轨迹交叉。</p> 
<p>现在给定一组确诊人员编号&#xff08;X1,X2,X3,...,Xn&#xff09;&#xff0c;在所有人当中&#xff0c;找出哪些人需要进行核酸检测&#xff0c;输出需要进行核酸检测的人数。&#xff08;注意&#xff1a;确诊病例自身不需要再做核酸检测&#xff09;</p> 
<p>需要进行核酸检测的人&#xff0c;是病毒传播链条上的所有人员&#xff0c;即有可能通过确诊病例所能传播到的所有人。</p> 
<p>例如&#xff1a;A是确诊病例&#xff0c;A和B有接触、B和C有接触、C和D有接触、D和E有接触&#xff0c;那么B\C\D\E都是需要进行核酸检测的人。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行为总人数 N</p> 
<p>第二行为确认病例人员编号&#xff08;确诊病例人员数量 &lt; N&#xff09;&#xff0c;用逗号分割</p> 
<p>第三行开始&#xff0c;为一个 N * N 的矩阵&#xff0c;表示每个人员之间是否有接触&#xff0c;0表示没有接触&#xff0c;1表示有接触。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>整数&#xff1a;需要做核酸检测的人数</p> 
<p></p> 
<h4>备注</h4> 
<ul><li>人员编号从0开始</li><li>0 &lt; N &lt; 100</li></ul> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">5<br /> 1,2<br /> 1,1,0,1,0<br /> 1,1,0,0,0<br /> 0,0,1,0,1<br /> 1,0,0,1,0<br /> 0,0,1,0,1</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>编号为1、2号的人员&#xff0c;为确诊病例。</p> <p>1号和0号有接触&#xff0c;0号和3号有接触。</p> <p>2号和4号有接触。</p> <p>所以&#xff0c;需要做核酸检测的人是0号、3号、4号&#xff0c;总计3人需要进行核酸检测。</p> </td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题可以用并查集解题。关于并查集的实现可以看&#xff1a;</p> 
<p><a href="https://fcqian.blog.csdn.net/article/details/127588130" rel="nofollow" title="华为校招机试 - 发广播&#xff08;20210310&#xff09;_华为机试 发广播 伏城之外-CSDN博客">华为校招机试 - 发广播&#xff08;20210310&#xff09;_华为机试 发广播 伏城之外-CSDN博客</a></p> 
<p></p> 
<p>即将有接触的人进行合并操作&#xff0c;纳入到同一个连通分量中。比如matrix[i]][j] &#61;&#61; 1&#xff0c;即 i 和 j 就处于同一个连通分量中&#xff0c;需要进行合并。</p> 
<p>另外&#xff0c;本题的接触关系矩阵matrix是沿对角线对称的&#xff0c;因此只需要遍历对角线一边即可。</p> 
<p>当遍历完所有接触关系后&#xff0c;就可以求解每一个连通分量中的节点数&#xff0c;即每个接触群体的人数&#xff0c;求解原理如下&#xff1a;</p> 
<blockquote> 
 <p>并查集底层的fa数组&#xff0c;fa数组索引代表每个节点&#xff0c;fa数组元素代表对应索引的节点的根节点&#xff0c;而同一个连通分量中的节点的根都是相同的&#xff0c;因此&#xff0c;我们需要对fa每一个数组索引找一下根&#xff0c;这里可以使用并查集的find操作&#xff08;递归实现&#xff09;&#xff0c;最后统计同一个根下的节点数量&#xff0c;即为同一个接触群体的人数。</p> 
</blockquote> 
<p></p> 
<p>当每个接触群体人数求解出来后&#xff0c;我们只需要统计”确诊病例人员编号“对应的根&#xff08;连通分量&#xff09;下的人数即可。</p> 
<p>最后的统计的总人数需要减去确诊病例的数量&#xff0c;因为题目说&#xff1a;</p> 
<blockquote> 
 <p>确诊病例自身不需要再做核酸检测</p> 
</blockquote> 
<p></p> 
<p>本题需要注意的是&#xff0c;有可能多个确诊病人在同一个连通分量重&#xff0c;此时需要注意避免重复统计。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  const n &#61; parseInt(await readline());
  const confirmed &#61; (await readline()).split(&#34;,&#34;).map(Number);

  const matrix &#61; [];
  for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
    matrix.push((await readline()).split(&#34;,&#34;).map(Number));
  }

  console.log(getResult(n, confirmed, matrix));
})();

class UnionFindSet {
  constructor(n) {
    this.fa &#61; new Array(n).fill(true).map((_, idx) &#61;&gt; idx);
  }

  // 查x站点对应的顶级祖先站点
  find(x) {
    while (x !&#61;&#61; this.fa[x]) {
      x &#61; this.fa[x];
    }
    return x;
  }

  // 合并两个站点&#xff0c;其实就是合并两个站点对应的顶级祖先节点
  union(x, y) {
    let x_fa &#61; this.find(x);
    let y_fa &#61; this.find(y);

    if (x_fa !&#61;&#61; y_fa) {
      // 如果两个站点祖先相同&#xff0c;则在一条链上&#xff0c;不需要合并&#xff0c;否则需要合并
      this.fa[y_fa] &#61; x_fa; // 合并站点&#xff0c;即让某条链的祖先指向另一条链的祖先
    }
  }
}

function getResult(n, confirmed, matrix) {
  const ufs &#61; new UnionFindSet(n);

  for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
    for (let j &#61; i; j &lt; n; j&#43;&#43;) {
      if (matrix[i][j] &#61;&#61; 1) {
        // 有过接触的人进行合并
        ufs.union(i, j);
      }
    }
  }

  // 统计每个接触群体&#xff08;连通分量&#xff09;中的人数
  const cnts &#61; new Array(n).fill(0);
  for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
    const fa &#61; ufs.find(i);
    cnts[fa]&#43;&#43;;
  }

  // 记录已统计过的感染群体
  const confirmed_fa &#61; new Set();

  // 将有感染者的接触群体的人数统计出来
  let ans &#61; 0;
  for (let i of confirmed) {
    const fa &#61; ufs.find(i);

    // 已统计过的感染群体不再统计
    if (confirmed_fa.has(fa)) continue;
    confirmed_fa.add(fa);

    ans &#43;&#61; cnts[fa];
  }

  // 最终需要做核酸的人数&#xff0c;不包括已感染的人
  return ans - confirmed.length;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; Integer.parseInt(sc.nextLine());

    int[] confirmed &#61; Arrays.stream(sc.nextLine().split(&#34;,&#34;)).mapToInt(Integer::parseInt).toArray();

    int[][] matrix &#61; new int[n][n];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      matrix[i] &#61; Arrays.stream(sc.nextLine().split(&#34;,&#34;)).mapToInt(Integer::parseInt).toArray();
    }

    System.out.println(getResult(n, confirmed, matrix));
  }

  public static int getResult(int n, int[] confirmed, int[][] matrix) {
    UnionFindSet ufs &#61; new UnionFindSet(n);

    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      for (int j &#61; i; j &lt; n; j&#43;&#43;) {
        if (matrix[i][j] &#61;&#61; 1) {
          // 有过接触的人进行合并
          ufs.union(i, j);
        }
      }
    }

    // 统计每个接触群体&#xff08;连通分量&#xff09;中的人数
    int[] cnts &#61; new int[n];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      int fa &#61; ufs.find(i);
      cnts[fa]&#43;&#43;;
    }

    // 记录已统计过的感染群体
    HashSet&lt;Integer&gt; confirmed_fa &#61; new HashSet&lt;&gt;();

    // 将有感染者的接触群体的人数统计出来
    int ans &#61; 0;
    for (int i : confirmed) {
      int fa &#61; ufs.find(i);

      // 如果该感染群体已统计过&#xff0c;则不再统计
      if (confirmed_fa.contains(fa)) continue;
      confirmed_fa.add(fa);

      ans &#43;&#61; cnts[fa];
    }

    // 最终需要做核酸的人数&#xff0c;不包括已感染的人
    return ans - confirmed.length;
  }
}

// 并查集实现
class UnionFindSet {
  int[] fa;

  public UnionFindSet(int n) {
    this.fa &#61; new int[n];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) fa[i] &#61; i;
  }

  public int find(int x) {
    if (x !&#61; this.fa[x]) {
      this.fa[x] &#61; this.find(this.fa[x]);
      return this.fa[x];
    }
    return x;
  }

  public void union(int x, int y) {
    int x_fa &#61; this.find(x);
    int y_fa &#61; this.find(y);

    if (x_fa !&#61; y_fa) {
      this.fa[y_fa] &#61; x_fa;
    }
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 并查集实现
class UnionFindSet:
    def __init__(self, n):
        self.fa &#61; [i for i in range(n)]

    def find(self, x):
        if x !&#61; self.fa[x]:
            self.fa[x] &#61; self.find(self.fa[x])
            return self.fa[x]
        return x

    def union(self, x, y):
        x_fa &#61; self.find(x)
        y_fa &#61; self.find(y)

        if x_fa !&#61; y_fa:
            self.fa[y_fa] &#61; x_fa


# 输入获取
n &#61; int(input())
confirmed &#61; list(map(int, input().split(&#34;,&#34;)))
matrix &#61; [list(map(int, input().split(&#34;,&#34;))) for _ in range(n)]


# 算法入口
def getResult():
    ufs &#61; UnionFindSet(n)

    for i in range(n):
        for j in range(i, n):
            if matrix[i][j] &#61;&#61; 1:
                # 有过接触的人进行合并
                ufs.union(i, j)

    # 统计每个接触群体&#xff08;连通分量&#xff09;中的人数
    cnts &#61; [0] * n
    for i in range(n):
        fa &#61; ufs.find(i)
        cnts[fa] &#43;&#61; 1

    # 记录已统计过的可能感染群体
    confirmed_fa &#61; set()

    # 将有感染者的接触群体的人数统计出来
    ans &#61; 0
    for i in confirmed:
        fa &#61; ufs.find(i)

        # 已统计过的可能感染群体不再统计
        if fa in confirmed_fa:
            continue
        confirmed_fa.add(fa)

        ans &#43;&#61; cnts[fa]

    # 最终需要做核酸的人数&#xff0c;不包括已感染的人
    return ans - len(confirmed)


# 算法调用
print(getResult())</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#define MAX_SIZE 100

/** 并查集定义 **/
typedef struct {
    int *fa;
} UFS;

UFS *new_UFS(int n) {
    UFS *ufs &#61; (UFS *) malloc(sizeof(UFS));

    ufs-&gt;fa &#61; (int *) malloc(sizeof(int) * n);
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
        ufs-&gt;fa[i] &#61; i;
    }

    return ufs;
}

int find_UFS(UFS *ufs, int x) {
    if (x !&#61; ufs-&gt;fa[x]) {
        ufs-&gt;fa[x] &#61; find_UFS(ufs, ufs-&gt;fa[x]);
        return ufs-&gt;fa[x];
    }
    return x;
}

void union_UFS(UFS *ufs, int x, int y) {
    int x_fa &#61; find_UFS(ufs, x);
    int y_fa &#61; find_UFS(ufs, y);

    if (x_fa !&#61; y_fa) {
        ufs-&gt;fa[y_fa] &#61; x_fa;
    }
}

int main() {
    int n;
    scanf(&#34;%d&#34;, &amp;n);

    int confirmed[MAX_SIZE];
    int confirmed_size &#61; 0;

    while (scanf(&#34;%d&#34;, &amp;confirmed[confirmed_size&#43;&#43;])) {
        if (getchar() !&#61; &#39;,&#39;) break;
    }

    UFS *ufs &#61; new_UFS(n);

    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
        for (int j &#61; 0; j &lt; n; j&#43;&#43;) {
            int v;
            scanf(&#34;%d&#34;, &amp;v);

            // 有过接触的人进行合并
            if (v &#61;&#61; 1) {
                union_UFS(ufs, i, j);
            }

            getchar();
        }
    }

    // 统计每个接触群体&#xff08;连通分量&#xff09;中的人数
    int cnts[MAX_SIZE] &#61; {0};
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
        int fa &#61; find_UFS(ufs, i);
        cnts[fa]&#43;&#43;;
    }

    // 记录已统计过的可能感染群体
    int confirmed_fa[MAX_SIZE] &#61; {0};

    // 将有感染者的接触群体的人数统计出来
    int ans &#61; 0;
    for (int i &#61; 0; i &lt; confirmed_size; i&#43;&#43;) {
        int fa &#61; find_UFS(ufs, confirmed[i]);

        // 已统计过的可能感染群体不再统计
        if(confirmed_fa[fa]) continue;
        confirmed_fa[fa] &#61; 1;

        ans &#43;&#61; cnts[fa];
    }

    // 最终需要做核酸的人数&#xff0c;不包括已感染的人
    printf(&#34;%d\n&#34;, ans - confirmed_size);

    return 0;
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>